This invention relates to the design of circuits with complex interconnections between circuit elements, and more particularly to methods for allocating interconnected circuit elements between two or more circuit element groups so that the number of interconnections required between the groups is minimized or at least substantially reduced, and methods for manipulating the methods of allocation of interconnected circuit elements to accomplish one or more design objectives.
In the design of large circuits, such as very large scale integrated ("VLSI") logic circuits, it is frequently necessary to subdivide the circuitry so that it can be implemented in two or more relatively discrete parts of one device or in two or more discrete devices. The circuit elements must be allocated between these two or more groups so that the number of interconnections required between the groups is not excessive. This systematic allocation of circuit elements is known as partitioning. One goal of partitioning is the reduction of interconnection between groups, because minimization of interconnections often results in a faster circuit, and because the number of interconnections is often a limiting factor in device resource utilization. An additional goal in partitioning is an even allocation of circuit elements among the groups so that the resources (e.g., space, etc.) in each group are utilized as efficiently as possible.
Partitioning has been extensively considered in the literature and prior art. See, for example, (1) B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", The Bell System Technical Journal, February 1970, pp. 291-307 (see also U.S. Pat. No. 3,617,714); (2) D. G. Schweikert and B. W. Kernighan, "A Proper Model for the Partitioning of Electrical Circuits", Proceedings of the 9th Design Automation Workshop, 1979, pp. 57-62; (3) C. M. Fiduccia and R. M. Mattheyses, "A Linear-Time Heuristic for Improving Network Partitions", 19th Design Automation Conference, 1982, pp. 241-47; (4) B. Krishnamurthy, "An Improved Min-Cut Algorithm for Partitioning VLSI Networks", IEEE Transactions on Computers, Vol. C-33, No. 5, May 1984, pp. 438-46; and (5) commonly assigned U.S. Pat. No. 5,341,308 of D. Mendel, entitled "Methods for Allocating Circuit Elements Between Groups," all of which are hereby incorporated by reference herein. Partitioning methods of the general type employed in the present invention are believed to have originated with reference (1) above, and to have progressed through additional enhancements in order with references (2), (3), (4), and (5). The present invention comprises further modifications and improvements to the techniques shown and described in reference (5).
As noted above, one goal of a partitioning method is to partition or divide a set of circuit elements or "cells" connected by wires into two or more circuit element groups such that the number of wires which cross from one group to the other is minimized or at least substantially reduced. Another goal of a partitioning method is to ensure that when the cells are placed into various circuit element groups, the distribution of the cells among the groups is as even as possible.
A circuit element group, as that term is employed herein, may be a discrete device such as an integrated circuit or a printed circuit board, or it may be a relatively discrete part of a larger device. For example, the two or more circuit element groups mentioned above may be two or more relatively discrete parts of a single integrated circuit such as a programmable logic array device. In the literature a set of cells connected by a common wire is generally referred to as a net. In at least the later references identified above (e.g., references (2)-(5)), a net can include any number of cells. Partitioning involves moving cells from one circuit element group to the other in an effort to reduce the number of connections required between the resulting circuit element groups.
The prior art (and the present invention) provides methods for allowing various solutions to the partitioning problem to be tried in a systematic way in order to more rapidly and efficiently find the circuit element moves which give the best result. The present invention further provides methods for manipulating partitioning schemes to accomplish various design goals.
In the above-mentioned prior art, partitioning generally consists of two phases. The first partitioning phase involves the initial placement of the cells into the circuit element groups. The second partitioning phase involves performing a partitioning operation (such as disclosed in references (4) and (5)) to re-allocate the placed cells among the circuit element groups to minimize the interconnections between circuit element groups.
The initial placement and the subsequent partitioning is subject to one or more "chip constraints" which may restrict or encourage particular cell placement or movement. The various chip constraints are described in the prior art references (1) through (5). One chip constraint which is particularly relevant to the present invention is the cell capacity (i.e., the room available for cell placement) in a particular circuit element group. Partitioning is also subject to one or more circuit constraints which include but are not limited to: the number of circuit element groups, maximum number of interconnections, requirements that certain circuit elements group be connected.
Partitioning is typically implemented by using one of two approaches for the first partitioning phase. In the first approach, a "random initial placement" is performed during the first phase. Random initial placement places cells into the circuit element groups randomly, only obeying the chip and circuit operation, such as disclosed in reference (4) or (5) is performed on the circuit element groups in order to improve the partition. The resulting partition is then saved, and the process may be repeated a number of times with each new partition being compared to the best (i.e., most advantageous) previously saved partition, so that the best partition of the two being compared is saved, while the inferior partition is discarded. The random initial placement approach has the advantage of allowing multiple starting positions for each partitioning operation pass and then allowing a choice of the best result from all the passes. However, partitioning using random initial placement has the disadvantage that the random starting positions may be far from the optimal partition for a particular set of circuit element groups. As a result, the partitioning operation may require an excessive number of passes to approach the optimal partition.
In the second approach, a "greedy initial placement" is performed during the first phase. Greedy initial placement places cells into the circuit element groups one at a time, with each placement decision being based on the position of the previously placed cell. Similarly to the first approach, greedy initial placement is also subject to circuit and chip constraints. During the second phase, a partitioning operation, such as disclosed in reference (4) or (5), is performed on the circuit element groups in order to improve the partition. The resulting partition is then saved.
Unlike the random initial placement approach, greedy initial placement does not have the ability to come up with different solutions on different passes of the partitioning operation. The greedy initial placement approach has the advantage of starting with a better partition than random initial placement, thus requiring less phase two partitioning to approach the optimal solution. However, during subsequent passes, reference (4) or (5) partitioning always starts partitioning in the same position, thus limiting the variation in resulting partitions.
It would therefore be desirable to combine the advantage of multiple starting positions of the random initial placement approach with the advantage of optimal starting positions of the greedy initial placement approach, without the disadvantages of either approach.
When partitioning cells into circuit element groups, the best partition found (in terms of minimized interconnections) may result in an uneven distribution of cells where some circuit element groups may be nearly full, while other groups may be less than half full. Thus, even an optimal partition with a minimal amount of interconnections may be inefficient in that while some circuit element groups are forced to support a large number of cells, other circuit element groups are not being fully utilized. The prior art references have attempted to deal with this problem by imposing an additional goal for partitioning in the form of a "balance" circuit constraint, which requires allocation of cells among the circuit element groups to be even. Thus, the balance constraint is intended to ensure that the resources (e.g., cell capacity, etc.) in each group are utilized as efficiently as possible.
Reference (5) provided an enhancement to the traditional balance constraint in the form of the ability to temporarily suspend the balance requirement to accomplish an advantageous cell placement, while restoring balance in later cell moves. Nevertheless, traditionally, the goal of maximization of chip and circuit resource utilization efficiency (via the balance constraint) and the goal of minimization of interconnections (via partitioning) were held to be of equal importance. However, the prior art references have failed to account for situations where one or the other partitioning goal is of secondary importance due to a particular design goal. For example, the design goal for a particular circuit may dictate that the circuit be optimized for speed regardless of resource utilization, thus making the balance constraint of secondary importance. A design goal for another circuit may dictate that efficient fitting of cells into circuit element groups is of primary importance, thus relegating the reduction of interconnections to a secondary role. This design goal is likely where a large amount of cells needs to be placed in a limited amount of circuit element groups. It would therefore be desirable to provide partitioning methods which allow the partitioning goals of interconnection minimization and resource utilization efficiency to be prioritized according to a design goal.
In prior art references (1)-(4) it was generally assumed that dividing the cells of a net between two circuit element groups requires an interconnection with two terminals: one for the output from one circuit element group, and one for the input to the other circuit element group. In addition, each interconnection may have one or more pins connected to it from the various input and output (I/O) ports of one or more cells in each circuit element group. When a particular cell is moved from one circuit element group to another during partitioning, the move may have one or more of the following results: no change in the number of I/O pins and interconnections, a new I/O pin may be added to or removed from an existing interconnection, a new interconnection may be created, or an existing interconnection may be eliminated.
To determine the total benefit of a particular cell move, the prior art references introduced the concept of a "gain cost function" (called "gain vector" in references (4) and (5)) which treated the creation of each new I/O pin or a new interconnection as a penalty, and each removal of an existing I/O pin or an existing interconnection as a benefit. A gain cost function for a particular cell move is derived by subtracting the total penalties of that cell move from the total benefits. For example, if a particular cell, when moved, creates one new I/O pin (one penalty), but removes two existing interconnections (two benefits), the gain cost function of the move would be one benefit. The objective of each move is to maximize the gain cost function.
However, the traditional gain maximization approach is problematic in that the penalties for creation and the benefits of removal of I/O pins (which are internal to each circuit element group) are equal in weight to the penalties for creation and the benefits of removal of interconnections (which connect the circuit element groups). For example, the removal of an I/O pin or the elimination of an interconnection results in one benefit. Reference (5) provided an enhancement to the traditional gain cost function by adjusting the benefits and penalties of cell moves when moving cells between circuit element groups which include connections external to the circuitry being partitioned. However, the prior art approaches to calculating the gain cost function fail to account for the fact that in practical circuit design, the elimination of interconnections between circuit element groups may be of greater importance than the elimination of I/O pins within a particular circuit element group. It would therefore be desirable to provide partitioning methods which allow a user to adjust the weight of the benefits for eliminating existing interconnections and the weight of the penalties for adding new interconnections in accordance with a design goal.
In view of the foregoing, it is an object of this invention to provide improved circuit partitioning methods.
It is a more particular object of the invention to provide circuit partitioning methods which combine the advantage of multiple starting positions of the random initial placement approach with the advantage of optimal starting positions of the greedy initial placement approach, without the disadvantages of either approach.
It is another more particular object of the invention to provide circuit partitioning methods which allow the partitioning goals of interconnection minimization and resource utilization efficiency to be prioritized according to a design goal.
It is still another more particular object of the invention to provide circuit partitioning methods which allow a user to adjust the weight of the benefits for eliminating existing interconnections and the weight of the penalties for adding new interconnections in accordance with a design goal.